Đầu tiên ghi lại một thế kỷ sau khi nó được cho là đã diễn ra, huyền thoại về việc thành lập Phnom Penh kể về một người phụ nữ địa phương, Penh (thường được gọi là Daun Penh ("Bà ngoại" hoặc "Bà già Penh") bằng tiếng Khmer), sống ở Chaktomuk, thuộc Phnom Penh ngày nay. Đó là vào cuối thế kỷ 14, khi ấy thủ đô Khmer vẫn còn ở Angkor gần Xiêm Riệp, cách Chaktomuk 350 km (217 mi) về phía bắc. Khi thu thập củi dọc theo bờ sông, bà Penh đã đuổi theo một cây koki nổi trên sông và đánh bắt nó từ dưới nước. Bên trong cái cây, bà tìm thấy bốn bức tượng Phật và một trong những Vishnu.

Phát hiện này được coi là một phước lành thiêng liêng, và với một số dấu hiệu cho thấy thủ đô Khmer đã được đưa đến Phnom Penh từ Angkor. Để xây dựng những vật linh thiêng mới, Penh đã dựng lên một ngọn đồi nhỏ trên bờ phía tây của sông Tonle Sap và để nó trong một ngôi đền, bây giờ được gọi là Wat Phnom ở phía bắc của trung tâm Phnom Penh. "Phnom" là tiếng Khmer cho "đồi" và đồi của Penh lấy tên của người sáng lập, và khu vực xung quanh nó được biết đến sau ngọn đồi.

Phnôm Pênh chính thức được chọn làm kinh đô của Campuchia từ thế kỷ 15 dưới triều vua Ponhea Yat khi kinh đô Angkor Thom bị quân Xiêm chiếm mất. Triều đình phải bỏ vùng Tây Bắc rút về Đông Nam lấy Phnôm Pênh làm bản doanh mới. Ngày nay trong số những mộ tháp phía sau Wat Phnom là tháp chứa di cốt Ponhea Yat cùng các hoàng thân. Chứng tích khác từ thời Angkor vàng son còn lưu lại là mấy pho tượng Phật ở Wat Phnom. Dù vậy mãi đến năm 1866 triều vua Norodom I thì Phnôm Pênh mới trở thành doanh sở dài lâu của Miên triều. Cung điện vua Miên được xây vào thời kỳ này, đánh dấu thời điểm khi ngôi làng nhỏ dần chuyển mình thành chốn đô hội.

Khi người Pháp sang lập nền Bảo hộ trên xứ Campuchia thì họ cũng cho đào kênh rạch, đắp đường sá, mở bến cảng thông thương. Đến thập niên 1920 thì cảnh quan đẹp đẽ của Phnôm Pênh đã khiến nơi này có mệnh danh là "Hòn ngọc châu Á". Trong 40 năm kế tiếp thành phố tiếp tục mở mang giao thông, nối đường sắt với hải cảng Sihanoukville và mở Sân bay Quốc tế Pochentong.

Trong thời kỳ Chiến tranh Việt Nam, lực lượng võ trang của phe cộng sản (Quân đội Nhân dân Việt Nam và Quân Mặt trận Dân tộc Giải phóng miền Nam Việt Nam) lấy đất Campuchia làm căn cứ và khu an toàn để đánh Việt Nam Cộng hòa và ủng hộ Khmer Đỏ, gây xáo trộn và bất an khiến hàng ngàn người Campuchia phải lánh miền quê, tản cư vào thành phố để tránh giao tranh. Chiến cuộc lan rộng. Đến năm 1975 thì dân số Phnôm Pênh đã lên 2 triệu dân, phản ảnh tình hình bất an ở nông thôn. Ngày 17 tháng 4 trùng ngày tết Khmer, thủ đô nước Cộng hòa Khmer thất thủ; quân Khmer Đỏ tiến chiếm được Phnôm Pênh. Chế độ này thi hành chính sách giải thể phố xá, dồn dân thành thị về miền quê lao động sản xuất. Thủ lĩnh Pol Pot dùng trường Trung học Chao Ponhea Yat thành nhà giam tra tấn và thủ tiêu mọi thành phần liên quan đến chính thể Cộng hòa Khmer cùng giới trí thức, chuyên môn. Nơi đó sau năm 1979 là Bảo tàng Toul Sleng cùng với Choeung Ek (Cánh Đồng Chết) cách Phnôm Pênh 15 km nay là hai nơi tưởng niệm những nạn nhân bị chế độ Khmer Đỏ sát hại.

Năm 1979, Quân đội Nhân dân Việt Nam đã tiến chiếm Phnôm Pênh, đánh bại Khmer Đỏ. Dân chúng sau đó mới dần hồi cư về thành phố. Phnôm Pênh lại khởi sắc, xây dựng lại. Đầu tư nước ngoài và ngoại viện trong những năm liên tiếp giúp chấn chỉnh lại thành phố. Một giai đoạn tái thiết bắt đầu, được thúc đẩy bởi sự ổn định liên tục của chính phủ, thu hút đầu tư nước ngoài mới và viện trợ của các nước bao gồm Pháp, Úc và Nhật Bản. Các khoản vay được thực hiện từ Ngân hàng Phát triển Châu Á và Ngân hàng Thế giới để phục hồi nguồn cung cấp nước sạch, đường sá và cơ sở hạ tầng khác. Dân số tăng đều từ 826.000 (1998) lên 1.3 triệu (2008).